#include <iostream>
#include "BTreeNode.h"
using namespace std;

//**************** Implementation of Class BTLeafNode *****************

/*
* Class constructor
* Reseve memory for the main memory buffer
*/
BTLeafNode::BTLeafNode(){	memset(buffer, 0, PageFile::PAGE_SIZE);}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	//Initialize a buffer in memory to 0
	memset (buffer, 0, PageFile::PAGE_SIZE);
	//Read value in memory to buffer
	return (pf.read (pid, buffer)); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	//Write value in buffer to PageFile
	return (pf.write(pid, buffer));
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int numKey = 0;	
	//Get the value in the first four bits of the buffer
	memcpy(&numKey, &buffer, sizeof(int));	
	return numKey ;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */ 
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = slotSize*getKeyCount() ;
	int currentKey, currentKeyCount;
	char* bufferPointer = &(buffer[0]);	
	char* temp = (char*)malloc(PageFile::PAGE_SIZE);
	memset(temp, 0, PageFile::PAGE_SIZE);

	if(getKeyCount() >= (PageFile::PAGE_SIZE - sizeof(int))/(sizeof(RecordId)+sizeof(int))) {
		cout << "Node is full!\n";	
		return RC_NODE_FULL;
	}
	
	bufferPointer += (sizeof(int) +sizeof(PageId));
	int i = 0;
	//Search for the correct location
	while (bufferPointer) {		
		memcpy(&currentKey, bufferPointer, sizeof(int));		
		//Move to the next slot	
		if (currentKey < key) {
			bufferPointer += slotSize;	
			i++;
		} 
		else //found		
			break;			
	}	
	if(totalSize > 0 && currentKey != 0) {		
		memcpy(temp, bufferPointer, totalSize - i*slotSize);		
		memset(bufferPointer, 0, totalSize - i*slotSize);	
	}	
	memcpy(bufferPointer, &key, sizeof(int));	
	bufferPointer += sizeof(int);	
	memcpy(bufferPointer, &rid, sizeof(RecordId));	
	bufferPointer += sizeof(RecordId);	
	if(totalSize > 0 && currentKey != 0) {		
		memcpy(bufferPointer, temp, totalSize - (slotSize * i));	
	}	
	free(temp);	
	
	currentKeyCount++;	
	bufferPointer = &(buffer[0]);	
	memcpy(bufferPointer, &currentKeyCount, sizeof(int));	
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	int i = 0, returnValue = 0;	
	RecordId r;		
	char* index = &(buffer[0]);	
	index += sizeof(int);	
	index += sizeof(PageId);	
	while(i < (getKeyCount() / 2)) {		
		index += slotSize;		
		i++;	
	}	

	char* temp = (char*)malloc(1024*sizeof(char));	
	char* head = temp;		
	memset(temp, 0, 1024*sizeof(char));	
	memcpy(temp, index, totalSize - (slotSize * (getKeyCount()/2)));

	memset(index, 0, totalSize - (slotSize * (getKeyCount()/2)));	
	int newKey = getKeyCount() / 2;	
	memcpy(buffer, &newKey, sizeof(int));

	while(temp) {		
		int k;		
		memcpy(&k, temp, sizeof(int));		
		if(k == 0) {			
			break;		
		}		
		temp += sizeof(int);		
		memcpy(&r, temp, sizeof(RecordId));		
		temp += sizeof(RecordId);		
		if(r.sid == 0 && r.pid == 0 && k != 272) {			
			int q = r.sid;			
			cout << "Invalid rid!" << endl;		
		}		
		if( sibling.insert(k, r) != 0 ) {			
			free(head);			
			return RC_FILE_WRITE_FAILED;		
		}	
	}	
	free(head);	

	if( sibling.readEntry(0, siblingKey, r) != 0) {		
		return RC_FILE_READ_FAILED;	
	}	
	
	if(key < siblingKey) {		
		if( insert(key, rid) != 0 ) {			
			return RC_FILE_WRITE_FAILED;		
		}	
	} 
	else {		
		if( sibling.insert(key, rid) != 0 ) {			
			return RC_FILE_WRITE_FAILED;		
		}	
	}	
	if( sibling.readEntry(0, siblingKey, r) != 0) {		
		return RC_FILE_READ_FAILED;	
	}	
	return returnValue;  }

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	char* index = &(buffer[0]);	
	int currentKey;	
	int i = 0;	
	index += sizeof(int);	
	while(index) {		
		memcpy(&currentKey, index, sizeof(int));		
		if(currentKey >= searchKey || currentKey == 0) {			
			eid = i;			
			break;		
		}		
		i++;		
		index += slotSize;	
	}	
	return 0;  
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	int slotSize = sizeof(RecordId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	char* index = &(buffer[0]);	
	int i = 0;	

	index += sizeof(int);	
	index += sizeof(PageId);	
	while(index && i < eid) {		
		index += slotSize;		
		i++;	
	}	
	memcpy(&key, index, sizeof(int));	
	index += sizeof(int);	
	memcpy(&rid, index, sizeof(RecordId));	
	return 0;  
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId pid;	
	char* index = &(buffer[0]);	
	index += sizeof(int);	
	memcpy(&pid, index, sizeof(PageId));	
	return pid; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	char* index = &(buffer[0]);	
	index += sizeof(int);	
	memcpy(index, &pid, sizeof(PageId));	
	return 0; 
}

//************** Implementation of Class BTNonLeafNode ******************

//Constructor
BTNonLeafNode::BTNonLeafNode() {memset(buffer, 0, PageFile::PAGE_SIZE);	}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	int returnValue = 0;		
	memcpy(&returnValue, &buffer, sizeof(int));	
	return returnValue;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int slotSize = sizeof(PageId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	char* index = &(buffer[0]);	
	int i = 0;	

	if(totalSize >= PageFile::PAGE_SIZE - sizeof(int)) {		
		cout << "Non-leaf node full" << endl;		
		return RC_NODE_FULL;	
	}	
	int currentKey;	
	while (index) {		
		memcpy(&currentKey, index, sizeof(int));		
			
		if (currentKey < key) {			
			index += slotSize;			
			i++;		
		} 
		else 			
			break;		
	}	
	if(currentKey == key) {					
		index += sizeof(int);		
		memcpy(index, &pid, sizeof(PageId));		
		return 0;	
	}	
	if (index == &(buffer[PageFile::PAGE_SIZE]))		
		return RC_FILE_WRITE_FAILED;

	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));	
	memset(temp, 0, PageFile::PAGE_SIZE);	

	if(totalSize > 0 && currentKey != 0) {		
		memcpy(temp, index, totalSize - (slotSize * i));		
		memset(index, 0, totalSize - (slotSize * i));	
	}	
	memcpy(index, &key, sizeof(int));	
	index += sizeof(int);	
	memcpy(index, &pid, sizeof(PageId));	
	index += sizeof(PageId);	
	if(totalSize > 0 && currentKey != 0) {		
		memcpy(index, temp, totalSize - (slotSize * i));	
	}	
	free(temp);
	int currentKeyCount = getKeyCount();	
	currentKeyCount++;	
	index = &(buffer[0]);	
	memcpy(index, &currentKeyCount, sizeof(int));	
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	int slotSize  = sizeof(PageId) + sizeof(int);	
	int totalSize = slotSize * getKeyCount();	
	int i = 0;	

	char* index = &(buffer[0]);	
	index += sizeof(int);  //Offset first four bytes

	while(i < (getKeyCount() / 2)) {		
		index += slotSize;		
		i++;	
	}	

	char* temp = (char*) malloc(PageFile::PAGE_SIZE);	
	char* head = temp;	
    int half = getKeyCount() / 2;	

	memset(temp, 0, PageFile::PAGE_SIZE);	
	memcpy(temp, index, totalSize - half);	

	memset(index, 0, totalSize - half);	
	memcpy(buffer, &half, sizeof(int));

	while(temp) {		
		int k;		
		PageId p;		
		memcpy(&k, temp, sizeof(int));		
		if(k == 0) {			
			break;		
		}		
		temp += sizeof(int);	//Offset first four bytes to store number of key	
		memcpy(&p, temp, sizeof(PageId));		
		temp += sizeof(PageId);		
		if( sibling.insert(k, p) != 0) {			
			free(head);			
			return RC_FILE_WRITE_FAILED;		
		}	
	}	
	free(head);	

	if(key < midKey) {		
		if( insert(key, pid) != 0 ){			
			return RC_FILE_WRITE_FAILED;		
		}	
	} 
	else {		
		if( sibling.insert(key, pid) != 0 ) {			
			return RC_FILE_WRITE_FAILED;		
		}	
	}	
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int slotSize = sizeof(PageId) + sizeof(int);	
	int totalSize = getKeyCount() * slotSize;	
	char* index = &(buffer[0]);	
	int curr_key;

	index += sizeof(int);	
	index += sizeof(int);	

	while(index) {		
		memcpy(&curr_key, index, sizeof(int));		
		if(curr_key != 0 && curr_key < searchKey) {			
			index += sizeof(int);				
		} 
		else {			
			index -= sizeof(PageId);			
			memcpy(&pid, index, sizeof(PageId));			
			break;		
		}		
		index += slotSize;	
	} 	
	return 0;	
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	char* index = &(buffer[0]);	
	int k = 1;	
	index += sizeof(int);

	memcpy(index, &pid1, sizeof(PageId));	
	index += sizeof(PageId);	
	memcpy(index, &key, sizeof(int));	
	index += sizeof(int);	
	memcpy(index, &pid2, sizeof(PageId));	
	memcpy(buffer, &k, sizeof(int));	
	return 0; 
}
